package tree;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName BaseBalanceTree.java
 * @Description TODO
 * @createTime 2020年08月20日 20:54:00
 */
public class BaseBalanceTree<E extends TreeComparable> extends BinarySearchTree<E>{
	public BaseBalanceTree(TreeComparable comparable) {
		super(comparable);
	}
	/**
	 * https://s1.ax1x.com/2020/08/12/ax23Af.png
	 */
	protected void rotateLeft(Node<E> grandParentNode) {
		Node<E> parent = grandParentNode.right;
		Node<E> child = parent.left;
		//g.right=p.left
		grandParentNode.right = parent.left;
		//p.left=g
		parent.left = grandParentNode;

		//设置p的根节点属性
		parent.parent = grandParentNode.parent;
		if (grandParentNode.isLeftChild()) {
			grandParentNode.parent.left = parent;
		} else if (grandParentNode.isRightChild()) {
			grandParentNode.parent.right = parent;
		} else {
			root = parent;
		}
		//设置t1的根节点
		if (child != null) {
			child.parent = grandParentNode;
		}
		//设置g的根节点
		grandParentNode.parent = parent;

		//更新高度
		updateHeight(grandParentNode);
		updateHeight(parent);
	}

	protected void rotateRight(Node<E> grandParentNode) {
		Node<E> parent = grandParentNode.left;
		Node<E> child = parent.right;
		grandParentNode.left = child;
		parent.right = grandParentNode;

		//设置p的根节点属性
		parent.parent = grandParentNode.parent;
		if (grandParentNode.isLeftChild()) {
			grandParentNode.parent.left = parent;
		} else if (grandParentNode.isRightChild()) {
			grandParentNode.parent.right = parent;
		} else {
			root = parent;
		}
		//设置t1的根节点
		if (child != null) {
			child.parent = grandParentNode;
		}
		//设置g的根节点
		grandParentNode.parent = parent;

		//更新高度
		updateHeight(grandParentNode);
		updateHeight(parent);
	}



	/**
	 * https://s1.ax1x.com/2020/08/16/dEFWfU.png
	 * 1. 最终结果d是根节点
	 * 2. a，b，c为左边子树，b为a，c根节点
	 * 3. e，f，g为左边子树，f为e，g根节点
	 */
	protected void rotate(Node<E> a, Node<E> b, Node<E> c,
						Node<E> d,
						Node<E> e, Node<E> f, Node<E> g,
						Node<E> r)//子树的根节点
	{
		//让d成为这子树的根节点
		d.parent=r.parent;
		if (r.isLeftChild()){
			r.parent.left=d;
		}else if (r.isRightChild()){
			r.parent.right=d;
		}else {
			root=d;
		}
		// a-b-c
		b.left=a;
		if (a !=null){
			a.parent=b;
		}
		b.right=c;
		if (c !=null){
			c.parent=b;
		}
		updateHeight(b);
		// e,f,g
		f.left=e;
		if (e!=null){
			e.parent=f;
		}
		f.right=g;
		if (g!=null){
			g.parent=f;
		}
		updateHeight(f);

		//b-d-f
		d.left=b;
		d.right=f;
		b.parent=d;
		f.parent=d;
		updateHeight(d);
	}

	protected void updateHeight(Node<E> b) {
	}

}
